// check pointer
owl_bool owl_check_bitarr_pointer(owl_byte * src, owl_umax size)
{
  return (src != NULL && size >= sizeof(owl_bitarr));
}

// check members
owl_bool owl_check_bitarr_members(owl_byte * ptr, owl_umax size, owl_umax left_pad, owl_umax num_bits)
{
  // reuse owl_check_mem_space_members()
  return (owl_check_mem_space_members(ptr, size)
          && (left_pad + num_bits) <= (size * OWL_BYTE_BITS)
          && num_bits != 0);
}

// check all
owl_bool owl_check_bitarr_all(owl_bitarr * data, owl_umax size)
{
  return owl_check_bitarr_pointer((void *) data, size) 
         && owl_check_bitarr_members(data -> arr -> ptr,
                                     data -> arr -> size,
                                     data -> left_pad,
                                     data -> num_bits);
}

// create a bitarr structure
owl_bitarr * owl_create_bitarr(owl_byte * data, owl_umax size, owl_umax left_pad, owl_umax num_bits)
{
  // check parameters
  owl_bitarr * new = NULL;
  owl_mem_space * sp = NULL;
  if (owl_check_bitarr_members(data, size, left_pad, num_bits) == owl_false)
    goto err;
    
  // create the structure
  new = (void *) owl_create_mem_space(sizeof(owl_bitarr)) -> ptr;
  if (new == NULL)
    goto err;
  // create the bytarr
  sp = (owl_mem_space *) owl_create_bytarr(data, size);
  if (sp == NULL)
    goto err;
  new -> arr = sp;
  // add the extra data
  new -> left_pad = left_pad;
  new -> num_bits = num_bits;
  
  // end
  return new; 
  err:
  owl_free_mem_space(&((owl_mem_space) {(void *) new, sizeof(owl_bitarr)}));
  owl_free_mem_space(new != NULL ? new -> arr : NULL);
  return NULL;
}

// function to free a bitarr structure
owl_umax owl_free_bitarr(owl_bitarr * bits)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false)
    return 0;
  
  // free the bytarr space
  owl_free_bytarr(bits -> arr);
  // free the structure space
  return owl_free_mem_space(&((owl_mem_space) {(void *) bits, sizeof(owl_bitarr)}));
}

// function to print a bitarr structure
owl_umax owl_print_bitarr(owl_byte * src, owl_umax size)
{
  // check params
  printf("OWL_BITARR struct info:\n");
  printf("  Struct info: %p, %llu\n", src, size);
  if (owl_check_bitarr_pointer(src, size) == owl_false)
    return 0;
  
  // otherwise print the contents of the bitarr
  owl_bitarr * bits = (void *) src;
  printf("  Byte pointer: %p\n", bits -> arr -> ptr);
  printf("  Number of bytes: %llu\n", bits -> arr -> size);
  printf("  Bytes (hex): ");
  for (owl_umax i = 0; i < (bits -> arr -> size); i++) {
    owl_print_byte_hex((bits -> arr -> ptr) + i, (bits -> arr -> size) - i);
    putchar(' ');
  }
  putchar('\n');
  // dedicated section to print the bits
  // actually pointed to by the structure data
  printf("  Left padding bits: %llu\n", bits -> left_pad);
  printf("  Number of bits: %llu\n", bits -> num_bits);
  printf("  Bits (bin): ");
  for (owl_umax i = 0; i < (bits -> arr -> size); i++) {
    for (owl_umax j = OWL_BYTE_BITS; j > 0; j--) {
      owl_umax bit_pos = (OWL_BYTE_BITS - j) + (i * OWL_BYTE_BITS);
      if (bit_pos == bits -> left_pad)
        putchar('[');
      putchar(((bits -> arr -> ptr)[i] & (1 << (j - 1))) != 0 ? '1' : '0');
      if (bit_pos == (bits -> left_pad) + (bits -> num_bits) - 1)
        putchar(']');
    }
    putchar(' ');
  }
  putchar('\n');
  return sizeof(owl_bitarr);
}

// compare 2 bitarrs
owl_char owl_comp_bitarr(owl_byte * bits1, owl_byte * bits2)
{
  // check params
  owl_bitarr * bits1_tmp = (void *) bits1,
             * bits2_tmp = (void *) bits2;
  // check params
  if (owl_check_bitarr_all(bits1_tmp, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitarr_all(bits2_tmp, sizeof(owl_bitarr)) == owl_false)
      return owl_comp_err;
  // do the comparison, size and byte contents matter
  // size has higher meaning than bit content
  // size
  if (bits1_tmp -> num_bits < bits2_tmp -> num_bits)
    return owl_comp_less;
  else if (bits1_tmp -> num_bits > bits2_tmp -> num_bits)
    return owl_comp_greater;
  // bit comparison if sizes are equal
  // first bit comparison to trigger the < or > expressions
  // get the start byte of each bitarr
  owl_umax byte1 = bits1_tmp -> left_pad / OWL_BYTE_BITS,
           byte2 = bits2_tmp -> left_pad / OWL_BYTE_BITS;
  owl_byte bit1_pos = bits1_tmp -> left_pad - (byte1 * OWL_BYTE_BITS) + 1,
           bit2_pos = bits2_tmp -> left_pad - (byte2 * OWL_BYTE_BITS) + 1;
  for (owl_umax i = 0; i < (bits1_tmp -> num_bits); i++) {
    // get ith bit from both bitrars and compare
    owl_byte bit1 = (bits1_tmp -> arr -> ptr)[byte1] & (1 << (OWL_BYTE_BITS - bit1_pos++)),
             bit2 = (bits2_tmp -> arr -> ptr)[byte2] & (1 << (OWL_BYTE_BITS - bit2_pos++));
    //~ printf("%u", bit1 >> (OWL_BYTE_BITS - bit1_pos + 1));
    if (bit1 < bit2) return owl_comp_less; 
    else if (bit1 > bit2) return owl_comp_greater; 
    // reset bit pos if major than 8, also, update new byte position
    if (bit1_pos > OWL_BYTE_BITS) {bit1_pos = 1; byte1++;} 
    if (bit2_pos > OWL_BYTE_BITS) {bit2_pos = 1; byte2++;} 
  }    
  // legit real equal bitarrs
  return owl_comp_equal;
}

// check bitshift_dir integer
owl_bool owl_check_bitshift_dir(owl_bitshift_dir shift)
{
  return (shift == OWL_BITSHIFT_LEFT || shift == OWL_BITSHIFT_RIGHT);
}

// function to calculate 4 integers 
// that are useful for some bitarr operations
struct owl_bitarr_extra_vars owl_get_bitarr_extra_vars(owl_bitarr * bits)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false)
    return (struct owl_bitarr_extra_vars) {0, 0, 0, 0, 0, 0};
  
  // get the position of the last and first byte
  owl_umax first_byte_pos = bits -> left_pad / OWL_BYTE_BITS,
           last_byte_pos = ((bits -> left_pad + bits -> num_bits) / OWL_BYTE_BITS);
  if ((bits -> left_pad + bits -> num_bits) % OWL_BYTE_BITS == 0) last_byte_pos--;
    
  // create the masks for both first and last bytes 
  // and also get the first and last bit's offsets
  owl_byte first_byte_mask = 0, last_byte_mask = 0;
  owl_umax first_bit_offset = bits -> left_pad,
           last_bit_offset = bits -> left_pad + bits -> num_bits - 1;
  while (owl_true) {
    if (first_bit_offset >= OWL_BYTE_BITS) first_bit_offset -= OWL_BYTE_BITS;
    if (last_bit_offset >= OWL_BYTE_BITS) last_bit_offset -= OWL_BYTE_BITS;
    if (first_bit_offset < OWL_BYTE_BITS && last_bit_offset < OWL_BYTE_BITS) break;
  }
  for (owl_byte i = 0; i < OWL_BYTE_BITS; i++) {
    first_byte_mask = (first_byte_mask << 1) + (i < first_bit_offset ? 1 : 0);
    last_byte_mask = (last_byte_mask << 1) + (i <= last_bit_offset ? 1 : 0);
  }
  last_byte_mask = ~last_byte_mask;
  
  // return the results
  return (struct owl_bitarr_extra_vars) {first_byte_pos, last_byte_pos,
                                         first_byte_mask, last_byte_mask,
                                         first_bit_offset, last_bit_offset};
}

// bitshift all the bits in a bitarr by 1 in one direction
owl_umax owl_bitshift(owl_bitarr * bits, owl_bitshift_dir shift)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitshift_dir(shift) == owl_false)
    return 0;
  
  // bitshift the bits
  // the real problems are the first and last bytes
  // I wont modify the bits outside the contents of the bitarr
  
  // get the extra variables from this function
  struct owl_bitarr_extra_vars a = owl_get_bitarr_extra_vars(bits);
  
  // grab what is not going to be moved from the first and last bytes
  owl_byte first_byte_save = (bits -> arr -> ptr)[a.first_byte_pos] & a.first_byte_mask,
           last_byte_save = (bits -> arr -> ptr)[a.last_byte_pos] & a.last_byte_mask;    
  // save the bits not going to be treated, then erase them
  (bits -> arr -> ptr)[a.first_byte_pos] &= ~(a.first_byte_mask);
  (bits -> arr -> ptr)[a.last_byte_pos] &= ~(a.last_byte_mask);
  //~ printf("\n%08b %08b\n", a.first_byte_mask, a.last_byte_mask);
  //~ printf("%u %u\n", a.first_byte_pos, a.last_byte_pos);
  //~ printf("%u %u\n", a.first_bit_offset, a.last_bit_offset);
  
  // do the bitshift
  owl_byte tmp1 = 0, tmp2 = 0;
  owl_umax byte_pos = a.first_byte_pos;  
  if (shift == OWL_BITSHIFT_RIGHT) {
    while (byte_pos - 1 != a.last_byte_pos) {
      tmp2 = (1 & (bits -> arr -> ptr)[byte_pos]) << (OWL_BYTE_BITS - 1);
      (bits -> arr -> ptr)[byte_pos] = ((bits -> arr -> ptr)[byte_pos] >> 1) + tmp1;
      tmp1 = tmp2;
      byte_pos++;
    }
    // clear possible bits overflowing outside the bitarr area (on the last byte)
    (bits -> arr -> ptr)[a.last_byte_pos] &= ~(a.last_byte_mask);
  }
  else /* shift == OWL_BITSHIFT_LEFT */ {
    byte_pos = a.last_byte_pos;
    while (byte_pos + 1 != a.first_byte_pos) {
      tmp2 = ((1 << (OWL_BYTE_BITS - 1)) & (bits -> arr -> ptr)[byte_pos]) >> (OWL_BYTE_BITS - 1);
      (bits -> arr -> ptr)[byte_pos] = ((bits -> arr -> ptr)[byte_pos] << 1) + tmp1;
      tmp1 = tmp2;
      byte_pos--;
    }
    // clear possible bits overflowing outside the bitarr area (on the first byte)
    (bits -> arr -> ptr)[a.first_byte_pos] &= ~(a.first_byte_mask);
  }
  
  // put back the byte data that was saved before the bitshift
  (bits -> arr -> ptr)[a.first_byte_pos] += first_byte_save;
  (bits -> arr -> ptr)[a.last_byte_pos] += last_byte_save;
  // done!
  return bits -> num_bits;
}

// do n bitshifts in a row 
owl_umax owl_n_bitshift(owl_bitarr * bits, owl_bitshift_dir shift, owl_umax n)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitshift_dir(shift) == owl_false
      || n == 0)
    return 0;
  
  // do the bitshift
  owl_umax tmp = n;
  while (tmp-- != 0) owl_bitshift(bits, shift);
  return n * bits -> num_bits;
}

// bitshift that keeps the bits that will be lost
owl_umax owl_circ_bitshift(owl_bitarr * bits, owl_bitshift_dir shift)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitshift_dir(shift) == owl_false)
    return 0;
  
  // get the extra variables from this function
  struct owl_bitarr_extra_vars a = owl_get_bitarr_extra_vars(bits);  
  // save the bit that is going to be lost
  owl_byte princess_bit = 0;
  if (shift == OWL_BITSHIFT_RIGHT) {
    princess_bit = (bits -> arr -> ptr)[a.last_byte_pos] & (1 << (OWL_BYTE_BITS - a.last_bit_offset - 1));
    princess_bit <<= a.last_bit_offset;
    princess_bit >>= a.first_bit_offset;
  } else /* shift == OWL_BITSHIFT_LEFT) */ {
    princess_bit = (bits -> arr -> ptr)[a.first_byte_pos] & (1 << (OWL_BYTE_BITS - a.first_bit_offset - 1));
    princess_bit <<= a.first_bit_offset;
    princess_bit >>= a.last_bit_offset;
  }
  // do the bitshift
  owl_bitshift(bits, shift);
  // add the lost bit
  if (shift == OWL_BITSHIFT_RIGHT)
    (bits -> arr -> ptr)[a.first_byte_pos] += princess_bit;
  else // shift == OWL_BITSHIFT_LEFT)
    (bits -> arr -> ptr)[a.last_byte_pos] += princess_bit;
  
  // done!
  return bits -> num_bits;
}

// do owl_circ_bitshift several times
owl_umax owl_n_circ_bitshift(owl_bitarr * bits, owl_bitshift_dir shift, owl_umax n)
{
    // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitshift_dir(shift) == owl_false
      || n == 0)
    return 0;
  
  // do the bitshift
  owl_umax tmp = n;
  while (tmp-- != 0) owl_circ_bitshift(bits, shift);
  return n * bits -> num_bits;
}

// set all the bits in a bitarr to 0 or 1
owl_umax owl_clear_bitarr(owl_bitarr * bits, owl_byte zero_or_one)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false
      || (zero_or_one != 0 && zero_or_one != 1))
    return 0;
  
  // get the extra variables
  struct owl_bitarr_extra_vars a = owl_get_bitarr_extra_vars(bits);
  
  // clear the bits
  for (owl_umax i = a.first_byte_pos; i <= a.last_byte_pos; i++) {
    owl_byte mask = 0;
    if (i == a.first_byte_pos)
      mask = (a.first_byte_pos == a.last_byte_pos) ? (a.first_byte_mask + a.last_byte_mask)
                                                   : a.first_byte_mask;
    else if (i == a.last_byte_pos)
      mask = a.last_byte_mask;
    (bits -> arr -> ptr)[i] &= mask;
    (bits -> arr -> ptr)[i] += (zero_or_one == 1) ? ~(mask) : 0;
  }
  
  // done!
  return bits -> num_bits; 
}

// get a new bitarr contained within a bitarr
owl_bitarr * owl_get_bits(owl_bitarr * src, owl_umax left_pad_offset, owl_umax new_num_bits)
{
  // check params
  if (owl_check_bitarr_all(src, sizeof(owl_bitarr)) == owl_false
      || new_num_bits == 0
      || left_pad_offset + new_num_bits > src -> num_bits)
    return NULL;
  
  // return the new structure
  return owl_create_bitarr(src -> arr -> ptr, src -> arr -> size,
                           src -> left_pad + left_pad_offset, new_num_bits);
}

// return a bitarr into its lowest size representation
// in other words, eliminate unnecesary left_pad bits (but keep the same alignment)
owl_bitarr * owl_normalize_bitarr(owl_bitarr * bits)
{
  // check params
  if (owl_check_bitarr_all(bits, sizeof(owl_bitarr)) == owl_false)
    goto err;
  
  // determine the variables of the new bitarr
  owl_umax arr_pos = bits -> left_pad / OWL_BYTE_BITS;
  owl_umax left_pad = bits -> left_pad - (arr_pos * OWL_BYTE_BITS);
  // num_bits remains the same
  owl_umax arr_size = ((left_pad + bits -> num_bits) / OWL_BYTE_BITS)
                      + ((left_pad + bits -> num_bits) % OWL_BYTE_BITS == 0 ? 0 : 1);
  
  // done!
  return owl_create_bitarr(bits -> arr -> ptr + arr_pos, arr_size, left_pad, bits -> num_bits);
  err:
  return NULL;
}

// write a bitarr into another bitarr (FIX SO IT DOES NOT COPY THE WHOLE ARRAY)
owl_bool owl_write_bits(owl_bitarr * src, owl_bitarr * dest)
{
  // check params
  owl_bitarr * tmp_bitarr = NULL;
  owl_mem_space * tmp_sp = NULL;
  if (owl_check_bitarr_all(src, sizeof(owl_bitarr)) == owl_false
      || owl_check_bitarr_all(dest, sizeof(owl_bitarr)) == owl_false)
    goto err;
  
  // - I need to make a temporal bitarr struct (tmp_bitarr, normalized version of src)
  // - align the bits on it so that they match dest's (erase unwanted bits from it)
  // - clear the bits on dest's bitarr section to be written
  // - do a simple += operation on the bytes from dest with the aligned content from tmp 
  
  // also, if dest -> num_bits < src -> num_bits the write 
  // will still be made but the non fitting data just wont be copied (useful in some cases)
  
  // this copy is useful and efficient when the source bits are not that many
  // if this generates problems in the future I can update it so the stuff
  // is directly copied to dest. It can get dirty.
  
  // get the normalized version of src and expand its 
  // contents by a single byte to allow for room for alignment
  tmp_bitarr = owl_normalize_bitarr(src);
  if (tmp_bitarr == NULL) goto err;
  tmp_sp = owl_create_mem_space(tmp_bitarr -> arr -> size + 1);
  if (tmp_sp == NULL) goto err;
  owl_copy_bytarr(&((owl_bytarr) {tmp_bitarr -> arr -> ptr, tmp_bitarr -> arr -> size}),
                  &((owl_bytarr) {tmp_sp -> ptr, tmp_sp -> size}));
  owl_free_mem_space(tmp_bitarr -> arr);
  tmp_bitarr -> arr = tmp_sp;
  
  // erase the bits that aren't going to be copied from tmp
  owl_umax tmp_umax1 = tmp_bitarr -> left_pad,
           tmp_umax2 = tmp_bitarr -> num_bits;
  tmp_bitarr -> left_pad = 0;
  tmp_bitarr -> num_bits = tmp_umax1;
  owl_clear_bitarr(tmp_bitarr, 0);
  tmp_bitarr -> left_pad = tmp_umax1 + tmp_umax2;
  tmp_bitarr -> num_bits = (tmp_bitarr -> arr -> size * OWL_BYTE_BITS) - (tmp_bitarr -> left_pad);
  owl_clear_bitarr(tmp_bitarr, 0);
  tmp_bitarr -> left_pad = tmp_umax1;
  tmp_bitarr -> num_bits = tmp_umax2;
  
  // align tmp's bits
  tmp_umax1 = tmp_bitarr -> left_pad;
  tmp_umax2 = tmp_bitarr -> num_bits;
  owl_umax dest_arr_pos = dest -> left_pad / OWL_BYTE_BITS;
  tmp_bitarr -> left_pad = 0;
  tmp_bitarr -> num_bits = tmp_bitarr -> arr -> size * OWL_BYTE_BITS;
  while ((dest -> left_pad - (dest_arr_pos * OWL_BYTE_BITS)) > tmp_umax1) {
    owl_bitshift(tmp_bitarr, OWL_BITSHIFT_RIGHT);
    tmp_umax1++;
  }
  while ((dest -> left_pad - (dest_arr_pos * OWL_BYTE_BITS)) < tmp_umax1) {
    owl_bitshift(tmp_bitarr, OWL_BITSHIFT_LEFT);
    tmp_umax1--;
  }
  tmp_bitarr -> left_pad = tmp_umax1;
  tmp_bitarr -> num_bits = tmp_umax2;
  
  // clear dest's bitarr to be written and write down the bit data
  owl_clear_bitarr(dest, 0);
  for (owl_umax i = 0; i < tmp_bitarr -> arr -> size; i++)
    (dest -> arr -> ptr)[dest_arr_pos + i] += (tmp_bitarr -> arr -> ptr)[i];
  
  // done!
  owl_free_bitarr(tmp_bitarr);
  return owl_true;
  err:
  owl_free_bitarr(tmp_bitarr);
  owl_free_mem_space(tmp_sp);
  return owl_false;
}
